package net.fkrahe.graph;

import br.ufrgs.inf.inf05005.automatos.AutomNode;
import br.ufrgs.inf.inf05005.utils.Utils;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * Class WLinked Graph (Weighted Linked Graph)
 * 
 * @author Yedidyah Langsan | Moshe Augenstein | Aaron M. Tenenbaum
 */
public class WLinkedGraph extends Graph {

    public WLinkedGraph() {
        super();
    }

    /**
     * Creates an arc between node1 and node2 with the given weight
     * 
     * @param infoObj1
     * @param infoObj2
     * @param weight 
     */
    public void join(Object infoObj1, Object infoObj2, String weight) {
        if (weight == null) {
            weight = "";
        }
        GraphNode gn1 = findNode(infoObj1);
        GraphNode gn2 = findNode(infoObj2);
        LinkedList<ArcNode> arcList = gn1.getArcptr();
        if (gn1 == null | gn2 == null) {
            if (Utils.DEBUG) {
                System.out.println("FU gn1 " + gn1 + " gn2 " + gn2 + " w " + weight);
            }
            return;
        } else {
            if (Utils.DEBUG) {
                System.out.println("OK gn1 " + gn1 + " gn2 " + gn2 + " w " + weight);
            }
        }
        WArcNode arcNode = new WArcNode(gn2, weight);

        // If the graph node is not connected to anything, create the arc
        if (arcList == null) {
            LinkedList<ArcNode> list = new LinkedList<ArcNode>();
            list.add(arcNode);
            gn1.setArcptr(list);
        } else if (arcList.isEmpty()) {
            arcList.add(arcNode);
        } else {

            Iterator<ArcNode> itrWAn = arcList.iterator();
            while (itrWAn.hasNext()) {
                WArcNode tmp = (WArcNode) itrWAn.next();
                if (tmp.equals(arcNode)) {
                    arcNode.setWeight(weight);
                    return;
                }
            }
            // connect node1 and node2
            arcList.addLast(arcNode);
        }
    }

    public boolean readWord(String entry) {
        // Guarda o nodo atual
        GraphNode nodo = this.getRoot();

        for (int i = 0; i < entry.length(); i++) {
            // um por um, pega as letras 
            String c = String.valueOf(entry.charAt(i));
            // procura na lista de arcos do nodo atual
            // pela transição correta;
            boolean found = false;
            LinkedList<ArcNode> listaArcos = nodo.getArcptr();
            if (listaArcos != null) {
                Iterator<ArcNode> itrListaArcos = listaArcos.iterator();
                while (itrListaArcos.hasNext()) {
                    WArcNode arco = (WArcNode) itrListaArcos.next();
                    if (arco.getWeight().equals(c)) {
                        nodo = arco.getPtr();
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    return false;
                }
            } else {
                return false;
            }
        }

        // a palavra foi "consumida". O nodo atual é final?
        AutomNode info = (AutomNode) nodo.getInfo();
        if (info.isIsFinal()) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * Return the weight on the arc between node1 and node2.
     * If node1 is not connected to node2 throws a
     * WLinkedGraphException
     * 
     * @param infoObj1
     * @param infoObj2
     * @return
     * @throws WLinkedGraphException 
     */
    public String getWeight(Object infoObj1, Object infoObj2) throws WLinkedGraphException {
        GraphNode gn1 = findNode(infoObj1);
        GraphNode gn2 = findNode(infoObj2);
        LinkedList<ArcNode> arcList = gn1.getArcptr();
        Iterator<ArcNode> itr = arcList.iterator();

        while (itr.hasNext()) {
            WArcNode arcNode = (WArcNode) itr.next();
            if (arcNode.getPtr() == gn2) {
                return arcNode.getWeight();
            }
        }
        // node 1 and node 2 are not connected
        throw new WLinkedGraphException(infoObj1.toString() + " is not connected to " + infoObj2.toString());
    }

    // automato
    public GraphNode getRoot() {
        return graphNodes.element();
    }

    public String getER() {
        WLinkedGraph graphCopy = getGraphCopy(this);
        graphCopy.singleFinalState();
        // System.out.println("Single final : " + graphCopy.toString());
        graphCopy.simplifyOr();
        // System.out.println("SimplifyOr: " + graphCopy.toString());

        // non-initial and non-final nodes should get simplified
        LinkedList<GraphNode> nodesToGo = new LinkedList<GraphNode>();

        Iterator<Object> itrInfo = graphCopy.nodes();
        while (itrInfo.hasNext()) {
            AutomNode n = (AutomNode) itrInfo.next();
            GraphNode gn = findNode(n);
            if (!n.isIsFinal() && !(gn.equals(graphCopy.getRoot()))) {
                nodesToGo.add(gn);
            }
        }

        // lets simplify them
        Iterator<GraphNode> itrToGo = nodesToGo.iterator();
        while (itrToGo.hasNext()) {
            GraphNode gn = itrToGo.next();
            graphCopy.contourNode(gn.getInfo());
            graphCopy.removeNode(gn.getInfo());
        }

        // montar a Expressão Regular
        // sai
        //RegularExpression re = new RegularExpression();
        // cria 4 strings: AutoQ0, q0qf, autoqf, qfq0
        String autoq0 = "";
        String q0qf = "";
        String autoqf = "";
        String qfq0 = "";
        Iterator<Object> itrNodes = graphCopy.nodes();
        while (itrNodes.hasNext()) {
            GraphNode gn = graphCopy.findNode(itrNodes.next());
            AutomNode info = (AutomNode) gn.getInfo();
            if (info.isIsFinal()) {
                // seta nome do nodo final
                // sai
//                re.setFinalState(info.getName());
                // seta autoFinal, direto na string
                // seta suas er's
                LinkedList<ArcNode> arcList = gn.getArcptr();
                if (arcList != null) {
                    Iterator<ArcNode> itrArcos = arcList.iterator();
                    while (itrArcos.hasNext()) {
                        WArcNode arco = (WArcNode) itrArcos.next();
                        // é sua auto-er?
                        if (arco.getPtr().equals(gn)) {
//                          re.setErFinal(arco.getWeight());
                            autoqf = arco.getWeight();
                            if (autoqf != null && !"".equals(autoqf)) {
                                autoqf = "(" + autoqf + ")*";
                            } else {
                                autoqf = "";
                            }

                        } else {
                            // é a ligacao qf->q0
                            //re.setErFinalInicial(arco.getWeight());
                            qfq0 = arco.getWeight();
                            if (qfq0 == null && "".equals(qfq0)) {
                                qfq0 = "";
                            } else {
                                qfq0 = "(" + qfq0 + ")";
                            }
                        }
                    }
                } else {
                    qfq0 = "";
                    autoqf = "";
                }
            } else {
                // seta nome do nodo final
                //re.setInitialState(info.getName());
                // seta suas er's
                Iterator<ArcNode> itrArcos = gn.getArcptr().iterator();
                while (itrArcos.hasNext()) {
                    WArcNode arco = (WArcNode) itrArcos.next();
                    // é sua auto-er?
                    if (arco.getPtr().equals(gn)) {
//                        re.setErInitial(arco.getWeight());
                        autoq0 = arco.getWeight();
                        if (autoq0 != null && !"".equals(autoq0)) {
                            autoq0 = "(" + autoq0 + ")*";
                        } else {
                            autoq0 = "";
                        }
                    } else {
                        // é a ligacao qf->q0
//                        re.setErInitialFinal(arco.getWeight());
                        q0qf = arco.getWeight();
                        if (q0qf == null || "".equals(q0qf)) {
                            q0qf = "";
                        } else {
                            q0qf = "(" + q0qf + ")";
                        }
                    }
                }
            }
        }

        if (!"".equals(qfq0)) {
            qfq0 = "(" + autoq0 + q0qf + autoqf + qfq0 + ")*";
        }

        // soma as string (com asterisco onde precisa) e retorna 
        return qfq0 + autoq0 + q0qf + autoqf;
    }

    /**
     * Remove a given node from graph.
     * 
     * @param node 
     */
    public void removeNode(Object node) {
        // remove all arcs
        Iterator<Object> objects = nodes();
        while (objects.hasNext()) {
            Object objTmp = objects.next();
            try {
                remove(objTmp, node);
            } catch (WLinkedGraphException ex) {
                // do nothing
            }
        }
        // remove node
        // System.out.println(graphNodes.toString());
        GraphNode gn = findNode(node);
//        if (gn != null) {
        graphNodes.remove(gn);
//        } else {
//            // System.out.println("WLinkedGraph.removeNode: shouldn't be null");
//        }
    }

    /**
     * Returns the weight on the arc between node1 and node2.
     * If node1 is not connected to node2 throws a WLinkedGraphException
     * 
     * @param node1
     * @param node2
     * @return
     * @throws WLinkedGraphException 
     */
    public String remove(Object node1, Object node2)
            throws WLinkedGraphException {
        // if node1 is not adjacent to node2, throw an exception
        if (!adjacent(node1, node2)) {
            throw new WLinkedGraphException(node1.toString() + " is not connected to " + node2.toString());
        }

        String w = getWeight(node1, node2);
        GraphNode gn1 = findNode(node1);
        GraphNode gn2 = findNode(node2);
        LinkedList<ArcNode> arcList = gn1.getArcptr();
        // node1 is not connected to anything, so there is
        // nothing to remove
        if (arcList == null || arcList.isEmpty()) {
            throw new WLinkedGraphException(node1.toString() + " is not connected to any other node.");
        }
        int pos = arcList.indexOf(new WArcNode(gn2, w));
        arcList.remove(pos);
        // System.out.println("$ Deleting arc @" + pos + " weighting " + w);
        return w;
    }

    /**
     * Creates a graph copy, so it can be manipulated without
     * destroying the original
     * 
     * @param graph
     * @return 
     */
    public WLinkedGraph getGraphCopy(WLinkedGraph graph) {
        WLinkedGraph novoGrafo = new WLinkedGraph();

        // copy nodes
        Iterator<GraphNode> itrOriginalNodes1 = graphNodes.iterator();
        while (itrOriginalNodes1.hasNext()) {
            // info velha
            GraphNode originalNode = itrOriginalNodes1.next();
            // info nova
            AutomNode originalInfo = (AutomNode) originalNode.getInfo();
            AutomNode novainfo = new AutomNode(originalInfo.getName(), originalInfo.isIsFinal());
            novoGrafo.add(novainfo);
        }

        // copy transitions
        Iterator<GraphNode> itrOriginalNodes2 = graphNodes.iterator();
        while (itrOriginalNodes2.hasNext()) {
            // original info
            GraphNode originalNode = itrOriginalNodes2.next();
            AutomNode originalInfo = (AutomNode) originalNode.getInfo();
            AutomNode newInfo1 = new AutomNode(originalInfo.getName(), originalInfo.isIsFinal());

            // pega os arcos
            LinkedList<ArcNode> listaArcosOriginal = originalNode.getArcptr();
            if (listaArcosOriginal != null) {
                Iterator<ArcNode> itrListaOriginalArcos = listaArcosOriginal.iterator();
                while (itrListaOriginalArcos.hasNext()) {
                    WArcNode arcoOriginal = (WArcNode) itrListaOriginalArcos.next();
                    GraphNode nodoDestinoOriginal = arcoOriginal.getPtr();
                    AutomNode infoDestinoOriginal = (AutomNode) nodoDestinoOriginal.getInfo();
                    AutomNode newInfo2 = new AutomNode(infoDestinoOriginal.getName(), infoDestinoOriginal.isIsFinal());
                    String newWeigth = arcoOriginal.getWeight();
                    // juntar os nodos
                    novoGrafo.join(newInfo1, newInfo2, newWeigth);
                }
            }

        }
        return novoGrafo;

        // original
//        WLinkedGraph graphBk = new WLinkedGraph();
//        LinkedList<GraphNode> finalNodesList = new LinkedList<GraphNode>();
//        // copy nodes
//        Iterator<AutomNode> itrNodes = this.nodes();
//        while (itrNodes.hasNext()) {
//            AutomNode tmp = itrNodes.next();
//            AutomNode newNode = new AutomNode(tmp.getName(), tmp.isIsFinal());
//            graphBk.add(newNode);
//            // quick test: is final?
//            if (newNode.isIsFinal()) {
//                finalNodesList.add(new GraphNode(newNode));
//            }
//        }
//        // copy transitions
//        Iterator<GraphNode> itrGraph = graphNodes.iterator();
//        while (itrGraph.hasNext()) {
//            GraphNode graphNode = itrGraph.next();
//            AutomNode node11nfo = (AutomNode) graphNode.getInfo();
//            String node1Name = node11nfo.getName();// nome nodo1
//
//            LinkedList<ArcNode> arcList = graphNode.getArcptr();
//            if (arcList != null) {
//                Iterator<ArcNode> itrArc = arcList.iterator();
//                while (itrArc.hasNext()) {
//                    WArcNode arc = (WArcNode) itrArc.next();
//                    String weight = arc.getWeight();// peso arco
//
//                    GraphNode node2 = arc.getPtr();
//                    AutomNode node2Info = (AutomNode) node2.getInfo();
//                    String node2Name = node2Info.getName();// nome próximo nodo
//
//                    graphBk.join(new AutomNode(node1Name), new AutomNode(node2Name), weight);
//                }
//            }
//        }
//        return graphBk;
    }

    /**
     * Create a single final state to the automata.
     * All previous final states become non-final and 
     * are connected to the new one.
     * 
     * @param graph
     * @return 
     */
    public void singleFinalState() {

        // Lista auxiliar, com todos os nodos que são finais
        LinkedList<GraphNode> finalNodesList = new LinkedList<GraphNode>();
        Iterator<AutomNode> itr = this.nodes();
        while (itr.hasNext()) {
            AutomNode tmp = itr.next();
            if (tmp.isIsFinal()) {
                finalNodesList.add(new GraphNode(tmp));
            }
        }

        // testar o tamanho da lista
        if (finalNodesList.size() == 0) {
            // System.out.println("WLinkedGraph.singleFinalState: Não existem estados finais");
        }

        /*
         * Se só há um nodo final, e ele não é inicial,
         * não é necessário fazer nada.
         * Só precisamos fazer novo final nos casos abaixo
         */
        AutomNode root = (AutomNode) getRoot().getInfo();
        if (finalNodesList.size() > 1 || root.isIsFinal()) {
            // ensure a unique name for final state, and add it
            String finalNodeName = "qf";
            while (this.add(new AutomNode(finalNodeName, true)) == false) {
                finalNodeName += "f";
            }
            // insert new final state
            GraphNode finalNode = this.findNode(new AutomNode(finalNodeName));
            AutomNode newFinalObj = (AutomNode) finalNode.getInfo();

            // mark all finals as non-final
            Iterator<GraphNode> itrFinalNodes = finalNodesList.iterator();
            while (itrFinalNodes.hasNext()) {
                GraphNode node = itrFinalNodes.next();
                AutomNode obj = (AutomNode) node.getInfo();
                obj.setIsFinal(false);// set not final
                this.join(obj, newFinalObj, null);
            }
        }
    }

    /**
     * Get a list of predecessor info-objects
     * 
     * @param graph
     * @param obj2
     * @return 
     */
    public LinkedList<Object> getPredecessors(Object obj2) {

        LinkedList<Object> predecessors = new LinkedList<Object>();
        Iterator<Object> objects = this.nodes();
        while (objects.hasNext()) {
            Object objTmp = objects.next();
            if (adjacent(objTmp, obj2) && !(objTmp.equals(obj2))) {
                predecessors.add(objTmp);
            }
        }
        return predecessors;
    }

    /**
     * Gets a regular expression representing all connections
     * from the node to itself
     * 
     * @param n
     * @return 
     */
    private String getAutoEr(GraphNode n) {
        String er = "";
        LinkedList<ArcNode> arcList = n.getArcptr();
        if (arcList == null) {
            return er;
        } else {
            Iterator<ArcNode> itrArcList = arcList.iterator();
            while (itrArcList.hasNext()) {
                WArcNode arco = (WArcNode) itrArcList.next();
                GraphNode apontado = arco.getPtr();
                if (apontado.equals(n)) {
                    er = joinStringWeight(er, arco.getWeight());
                }
            }
        }
        // return er
        if ("".equals(er)) {
            return er;
        } else {
            return er + "*";
        }
    }

    /**
     * 
     * From this
     *         |---------------------|
     *         |                     |
     *        q1             >P1<--| |
     *          \           /      | |
     *           \Q1     P1/       | |
     *            \   S   /        | |
     *             \  ^  /         | |
     *              > s            | |
     *             /    \          | |
     *            /      \         | |
     *           /Qk      \Pm      | |
     *          /          \       | |
     *        qk--------->  >Pm<-----|
     *         |    Rkm            |
     *         |--------------------
     * 
     * To this
     * 
     *             R11 + Q1 S* P1
     *        q1------------------->P1
     *          \                 />
     *           \         /-----/ Rk1 + Qk S* Pm
     *            \       /
     *             \------------
     *                  /       \
     *           /------         \ R1m + Q1 S* Pm
     *          /                 >
     *        qk------------------->Pm
     *             Rkm + Qk S* Pm
     * 
     * From: Hopcroft | Ullman | Motwani - Introduction to Automata Theory, Languages, and Computation. Ed. Addison-Wesley. Page 105 (pt_BR edition)
     * 
     * @param graph
     * @return a regular expression
     */
    public void contourNode(Object info) {

        GraphNode node = findNode(info);

        String S = getAutoEr(node);

        GraphNode s = findNode(info);
        LinkedList<ArcNode> pArcs = null;
        if (s != null) {
            pArcs = s.getArcptr();
        }

        // iterate through predecessors
        LinkedList<Object> predec = getPredecessors(info);
        Iterator<Object> itrObjPred = predec.iterator();
        while (itrObjPred.hasNext()) {

            AutomNode qInfoPred = (AutomNode) itrObjPred.next();
            GraphNode qGNodePred = this.findNode(qInfoPred);

            WArcNode q2sWArc = (WArcNode) qGNodePred.getArc(s);
            String Q = q2sWArc.getWeight();

            if (pArcs != null) {

                // iterate through sucessors
                Iterator<ArcNode> itrPArc = pArcs.iterator();
                while (itrPArc.hasNext()) {

                    WArcNode pArc = (WArcNode) itrPArc.next();
                    GraphNode pGNode = pArc.getPtr();
                    AutomNode pInfo = (AutomNode) pGNode.getInfo();

                    String P = pArc.getWeight();

                    // in
                    if (adjacent(qInfoPred, pInfo)) {
                        WArcNode rWArc = (WArcNode) qGNodePred.getArc(pGNode);
                        String R;
                        try {
                            R = getWeight(qInfoPred, pInfo);
                            remove(qInfoPred, pInfo);
                            String er = "(" + R + "+" + Q + S + P + ")";
                            join(qInfoPred, pInfo, er);
                        } catch (WLinkedGraphException ex) {
                            // System.out.println("WLinkedGraph.contourNode: never should get here, if they are adjacent");
                        }
                    } else {
                        String er = "(" + Q + S + P + ")";
                        join(qInfoPred, pInfo, er);
                    }
                }

            } else {
                removeNode(info);
            }
        }
    }

    private void simplifyOr() {
        // pegar um iterator para o grafo e
        // simplificar cada nodo
        Iterator<GraphNode> itrNodos = graphNodes.iterator();
        while (itrNodos.hasNext()) {
            // pegar um nodo
            GraphNode nodo = itrNodos.next();

            // criar uma lista auxiliar de arcos
            LinkedList<ArcNode> novaListaArcos = new LinkedList<ArcNode>();

            // pegar os arcos do nodo em questão
            LinkedList<ArcNode> listaVelhaDeArcos = nodo.getArcptr();
            if (listaVelhaDeArcos != null) {
                Iterator<ArcNode> itrListaVelha = listaVelhaDeArcos.iterator();
                while (itrListaVelha.hasNext()) {
                    // pegar um arco do nodo
                    WArcNode arcoVelho = (WArcNode) itrListaVelha.next();
                    /*
                     * SE o cara apontado por este arco
                     * já for apontado por algum arco da lista,
                     * fazer update no arco da lista e remover este arco
                     * SENÃO
                     * adiciona o arco na lista
                     */
                    GraphNode apontado = arcoVelho.getPtr();
                    // iterar na lista auxiliar, 
                    // verificando se tem alguém apontando para esse nodo
                    Iterator<ArcNode> itrNovaLista = novaListaArcos.iterator();
                    boolean continhaAlguemApontando = false;
                    while (itrNovaLista.hasNext()) {
                        WArcNode novoArco = (WArcNode) itrNovaLista.next();
                        if (novoArco.ptr.equals(apontado)) {
                            continhaAlguemApontando = true;
                            // descobrir novo peso
                            String pesoArcoNovo = novoArco.getWeight();
                            String pesoArcoVelho = arcoVelho.getWeight();
                            String novoPeso = joinStringWeight(pesoArcoNovo, pesoArcoVelho);
                            // setar novo peso no  arco da lista auxiliar
                            novoArco.setWeight(novoPeso);
                            // deletar arco apontado (secundario)
                        }
                    }
                    // devo inserir o arco na lista auxiliar?
                    if (!continhaAlguemApontando) {
                        novaListaArcos.add(arcoVelho);
                    }
                }
                // agora, o nodo mantém apenas a lista auxiliar de arcos
                nodo.setArcptr(novaListaArcos);
            }
        }
    }

    private String joinStringWeight(String weight1, String weight2) {
        if ("".equals(weight1) || "".equals(weight2)) {
            if ("".equals(weight1)) {
                return weight2;
            } else {
                return weight1;
            }
        } else {
            return weight1 + "+" + weight2;
        }
    }
}
